package com.dyw.Day21;

import java.util.Arrays;

/**
 * @author Devil
 * @create 2022-02-03-23:00
 *
 *
 * 计数质数
 * 统计所有小于非负整数 n 的质数的数量。
 *
 * 方法: 埃氏筛
 * 埃氏筛，就是先将 prime 数组全部赋值为 1。(记得将 prime1 赋值为 0 )。
 * 仍然是要从 1 枚举到 n 。我们先假设当前枚举到了 i 。
 *
 * 如果 primei=1 也就是 i 为质数，则我们可以知道 i 的倍数均为合数，所以我们就将 primei×k<n,k>=2 赋值为 0 。
 */
@SuppressWarnings("all")
public class Demo02 {
    public static void main(String[] args) {
        new Demo02().countPrimes(0);
    }
    public int countPrimes(int n) {
        int count = 0;
        if (n<=0){
            return 0;
        }
        int[] prime = isPrime(n);
        for (int i = 1; i < prime.length-1; i++) {
            if(prime[i]==1){
                count++;
            }
        }
        return count;
    }
    public int[] isPrime(int n){
        int[] prime = new int[n];
        memSet(prime);
        for (int i = 1; i < prime.length; i++) {
            if(prime[i]==1){
                //如果prime[i]是素数那么他的倍数就是合数
                for (int j = 2; i*j <= n; j++) {
                    prime[i*j]=0;
                }
            }
        }
        return prime;
    }
    public void memSet(int[] prime){
        Arrays.fill(prime,1);//这里时jdk自带的数组工具类作用就是将数组 全部填充为1;
        prime[1]=0;
    }


}
